Search Results

Documents authored by Weber, Simon

Document
DOI: 10.4230/LIPIcs.ISAAC.2023.15
An FPT Algorithm for Splitting a Necklace Among Two Thieves

Authors: Michaela Borzechowski, Patrick Schnider, and Simon Weber

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

Abstract
It is well-known that the 2-Thief-Necklace-Splitting problem reduces to the discrete Ham Sandwich problem. In fact, this reduction was crucial in the proof of the PPA-completeness of the Ham Sandwich problem [Filos-Ratsikas and Goldberg, STOC'19]. Recently, a variant of the Ham Sandwich problem called α-Ham Sandwich has been studied, in which the point sets are guaranteed to be well-separated [Steiger and Zhao, DCG'10]. The complexity of this search problem remains unknown, but it is known to lie in the complexity class UEOPL [Chiu, Choudhary and Mulzer, ICALP'20]. We define the analogue of this well-separation condition in the necklace splitting problem - a necklace is n-separable, if every subset A of the n types of jewels can be separated from the types [n]⧵A by at most n separator points. Since this version of necklace splitting reduces to α-Ham Sandwich in a solution-preserving way it follows that instances of this version always have unique solutions. We furthermore provide two FPT algorithms: The first FPT algorithm solves 2-Thief-Necklace-Splitting on (n-1+𝓁)-separable necklaces with n types of jewels and m total jewels in time 2^O(𝓁log𝓁) + O(m²). In particular, this shows that 2-Thief-Necklace-Splitting is polynomial-time solvable on n-separable necklaces. Thus, attempts to show hardness of α-Ham Sandwich through reduction from the 2-Thief-Necklace-Splitting problem cannot work. The second FPT algorithm tests (n-1+𝓁)-separability of a given necklace with n types of jewels in time 2^O(𝓁²) ⋅ n⁴. In particular, n-separability can thus be tested in polynomial time, even though testing well-separation of point sets is co-NP-complete [Bergold et al., SWAT'22].
Cite as

Michaela Borzechowski, Patrick Schnider, and Simon Weber. An FPT Algorithm for Splitting a Necklace Among Two Thieves. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 15:1-15:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{borzechowski_et_al:LIPIcs.ISAAC.2023.15,
  author =	{Borzechowski, Michaela and Schnider, Patrick and Weber, Simon},
  title =	{{An FPT Algorithm for Splitting a Necklace Among Two Thieves}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{15:1--15:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.15},
  URN =		{urn:nbn:de:0030-drops-193178},
  doi =		{10.4230/LIPIcs.ISAAC.2023.15},
  annote =	{Keywords: Necklace splitting, n-separability, well-separation, ham sandwich, FPT}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.30
On Connectivity in Random Graph Models with Limited Dependencies

Authors: Johannes Lengler, Anders Martinsson, Kalina Petrova, Patrick Schnider, Raphael Steiner, Simon Weber, and Emo Welzl

Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)

Abstract
For any positive edge density p, a random graph in the Erdős-Rényi G_{n,p} model is connected with non-zero probability, since all edges are mutually independent. We consider random graph models in which edges that do not share endpoints are independent while incident edges may be dependent and ask: what is the minimum probability ρ(n), such that for any distribution 𝒢 (in this model) on graphs with n vertices in which each potential edge has a marginal probability of being present at least ρ(n), a graph drawn from 𝒢 is connected with non-zero probability? As it turns out, the condition "edges that do not share endpoints are independent" needs to be clarified and the answer to the question above is sensitive to the specification. In fact, we formalize this intuitive description into a strict hierarchy of five independence conditions, which we show to have at least three different behaviors for the threshold ρ(n). For each condition, we provide upper and lower bounds for ρ(n). In the strongest condition, the coloring model (which includes, e.g., random geometric graphs), we show that ρ(n) → 2-ϕ ≈ 0.38 for n → ∞, proving a conjecture by Badakhshian, Falgas-Ravry, and Sharifzadeh. This separates the coloring models from the weaker independence conditions we consider, as there we prove that ρ(n) > 0.5-o(n). In stark contrast to the coloring model, for our weakest independence condition - pairwise independence of non-adjacent edges - we show that ρ(n) lies within O(1/n²) of the threshold 1-2/n for completely arbitrary distributions.
Cite as

Johannes Lengler, Anders Martinsson, Kalina Petrova, Patrick Schnider, Raphael Steiner, Simon Weber, and Emo Welzl. On Connectivity in Random Graph Models with Limited Dependencies. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 30:1-30:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{lengler_et_al:LIPIcs.APPROX/RANDOM.2023.30,
  author =	{Lengler, Johannes and Martinsson, Anders and Petrova, Kalina and Schnider, Patrick and Steiner, Raphael and Weber, Simon and Welzl, Emo},
  title =	{{On Connectivity in Random Graph Models with Limited Dependencies}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{30:1--30:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.30},
  URN =		{urn:nbn:de:0030-drops-188556},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.30},
  annote =	{Keywords: Random Graphs, Independence, Dependency, Connectivity, Threshold, Probabilistic Method}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact